home *** CD-ROM | disk | FTP | other *** search
/ HPAVC / HPAVC CD-ROM.iso / VELENG10.ZIP / PBSOLVER.C < prev    next >
C/C++ Source or Header  |  1997-07-27  |  10KB  |  403 lines
  1. // ****************************************************************************
  2. // *                                                                          *
  3. // *                      Velena Source Code V1.0                             *
  4. // *                   Written by Giuliano Bertoletti                         *
  5. // *       Based on the knowledged approach of Louis Victor Allis             *
  6. // *   Copyright (C) 1996-97 by Giuliano Bertoletti & GBE 32241 Software PR   *
  7. // *                                                                          *
  8. // ****************************************************************************
  9.  
  10. // Portable engine version.
  11. // read the README file for further informations.
  12.  
  13. // ==========================================================================
  14.  
  15.  
  16. #include <stdio.h>
  17. #include <string.h>
  18. #include <stdlib.h>
  19. #include <malloc.h>
  20.  
  21.  
  22. #include "connect4.h"
  23. #include "con4vals.h"
  24.  
  25. #include "rules.h"
  26. #include "pnsearch.h"
  27. #include "proto.h"
  28.  
  29. short tempsolused;
  30. char *wside[]={"none","yellow","red"};
  31.  
  32.  
  33. struct problem {
  34.                     short group;
  35.                     short solved;
  36.                     short solutions[ALLOC_SOLUTIONS];
  37.                     short solnumb;
  38.                     };
  39.  
  40.  
  41. struct problem_list {
  42.                           short number;
  43.                           struct problem *problem[GROUPS];
  44.                           short pointer[GROUPS];
  45.                           short final[GROUPS];
  46.                           };
  47.  
  48. struct up_solution {
  49.                          short howmany;
  50.                          short *which;
  51.                          short hmprobs;
  52.                          short *wprobs;
  53.                          };
  54.  
  55. extern char *rulename[];
  56.  
  57.  
  58. void dump_ddebug(struct board *board,struct problem_list *pblist,short j)
  59.     {
  60.     short x,y,name,px,py,qx,qy,i,k;
  61.     FILE *h1;
  62.  
  63.     h1=fopen("DEBUG.LOG","a+");
  64.     if(!h1) fatal_error("Cannot debug!");
  65.  
  66.     fprintf(h1,"\n");
  67.  
  68.     for(x=0;x<tempsolused;x++)
  69.         putc(0x09,h1);
  70.  
  71.     fprintf(h1,"Problem [%2d] %c%d-%c%d\n",j,
  72.         board->xplace[pblist->problem[j]->group][0]+97,board->yplace[pblist->problem[j]->group][0]+1,
  73.         board->xplace[pblist->problem[j]->group][3]+97,board->yplace[pblist->problem[j]->group][3]+1);
  74.  
  75.     fclose(h1);
  76.     }
  77.  
  78.  
  79. void dump_debug(struct board *board,struct problem_list *pblist,short j)
  80.     {
  81.     short x,y,name,px,py,qx,qy,i,k;
  82.     FILE *h1;
  83.  
  84.     h1=fopen("DEBUG.LOG","a+");
  85.     if(!h1) fatal_error("Cannot debug!");
  86.  
  87.     for(x=0;x<tempsolused;x++)
  88.         putc(0x09,h1);
  89.  
  90.     fprintf(h1,"PG[%2d] %c%d-%c%d  --> sol. ",j,
  91.         board->xplace[pblist->problem[j]->group][0]+97,board->yplace[pblist->problem[j]->group][0]+1,
  92.         board->xplace[pblist->problem[j]->group][3]+97,board->yplace[pblist->problem[j]->group][3]+1);
  93.  
  94.     i=pblist->final[j];
  95.     if(i==-1) fprintf(h1,"    NOT FOUND\n");
  96.     else
  97.         {
  98.         name=board->solution[i]->solname;
  99.         px=ELX(board->solution[i]->solpoint[0]);
  100.         py=ELY(board->solution[i]->solpoint[0]);
  101.  
  102.         qx=ELX(board->solution[i]->solpoint[1]);
  103.         qy=ELY(board->solution[i]->solpoint[1]);
  104.  
  105.         fprintf(h1,"%13s  ",rulename[name-1]);
  106.         fprintf(h1,"%c%d-%c%d   ",px+97,py+1,qx+97,qy+1);
  107.         fprintf(h1,"[%03d] {",i);
  108.  
  109.         for(y=0;y<board->solution[i]->sqinvnumb;y++)
  110.             {
  111.             k=board->solution[i]->sqinv[y];
  112.             fprintf(h1," %c%d",ELX(k)+97,ELY(k+1)+1);
  113.             }
  114.  
  115.         fprintf(h1," }\n");
  116.         }
  117.  
  118.     fclose(h1);
  119.     }
  120.  
  121.  
  122.  
  123. void find_most_difficult_problem(struct problem_list *pblist,short *minsol,short *solpnt,struct board *board)
  124.     {
  125.     short i,j,k,m;
  126.  
  127.     *minsol=32767;
  128.     *solpnt=-1;
  129.  
  130.     for(i=0;i<pblist->number;i++)
  131.         {
  132.         if(!pblist->problem[i]->solved)
  133.             {
  134.             k=0;
  135.             for(j=0;j<pblist->problem[i]->solnumb;j++)
  136.                 {
  137.                 m=pblist->problem[i]->solutions[j];
  138.                 if(board->solution[m]->valid) k++;
  139.                 }
  140.  
  141.             if(k<(*minsol))
  142.                 {
  143.                 *minsol=k;
  144.                 *solpnt=i;
  145.                 }
  146.             }
  147.         }
  148.     }
  149.  
  150.  
  151. void build_problem_list(struct problem_list *pblist,struct board *board)
  152.     {
  153.     short i,j=0,x,y;
  154.  
  155.     for(i=0;i<GROUPS;i++)
  156.         {
  157.         pblist->final[i]=-1;
  158.  
  159.         if(board->intgp.tgroups[i]==YES)
  160.             {
  161.             pblist->problem[j]=(struct problem *)malloc(sizeof(struct problem));
  162.             if(!pblist->problem[j]) fatal_error("Not enough memory to build problem list");
  163.  
  164.             pblist->pointer[i]=j;
  165.             pblist->problem[j]->group=i;
  166.             pblist->problem[j]->solnumb=0;
  167.             pblist->problem[j]->solved=NO;
  168.  
  169.             pblist->number=++j;
  170.             }
  171.  
  172.         else pblist->pointer[i]=-1;
  173.         }
  174.  
  175.     for(x=0;x<board->sp;x++)
  176.         {
  177.         board->solution[x]->valid=YES;
  178.         for(y=0;y<board->solution[x]->solgroupsnumb;y++)
  179.             {
  180.             i=board->solution[x]->solgroups[y];
  181.             j=pblist->pointer[i];
  182.  
  183.             pblist->problem[j]->solutions[pblist->problem[j]->solnumb++]=x;
  184.             }
  185.         }
  186.     }
  187.  
  188. void remove_problem_list(struct problem_list *pblist)
  189.     {
  190.     short x;
  191.  
  192.     for(x=0;x<pblist->number;x++)
  193.         free(pblist->problem[x]);
  194.     }
  195.  
  196. void remove_solutions(struct up_solution *update,struct problem_list *pblist,
  197.                              struct board *board,char **matrix,short psol)
  198.     {
  199.     short x,y,z,j,ps;
  200.     short tsol=0,*temp,*tprobs;
  201.     short probs=0;
  202.  
  203.     temp=(short *)malloc(MAXSOLS*sizeof(short));
  204.     tprobs=(short *)malloc(GROUPS*sizeof(short));
  205.     if(!temp || !tprobs) fatal_error("Not enough memory!");
  206.  
  207.     for(y=0;y<board->solution[psol]->solgroupsnumb;y++)
  208.         {
  209.         z=board->solution[psol]->solgroups[y];
  210.         j=pblist->pointer[z];
  211.         if(j==-1) fatal_error("No real problem found");
  212.  
  213.         if(!pblist->problem[j]->solved)
  214.             {
  215.             pblist->problem[j]->solved=YES;
  216.             tprobs[probs++]=j;
  217.             pblist->final[j]=psol;
  218.             }
  219.         }
  220.  
  221.  
  222.     for(x=0;x<board->sp;x++)
  223.         {
  224.         if(x>psol) ps=matrix[x][psol];
  225.         else ps=matrix[psol][x];
  226.  
  227.         if(ps==NO && board->solution[x]->valid)
  228.             {
  229.             board->solution[x]->valid=NO;
  230.             temp[tsol++]=x;
  231.             }
  232.         }
  233.  
  234.     if(tsol>=MAXSOLS) fatal_error("Wrote beyond buffer allocation");
  235.  
  236.     update->howmany=tsol;
  237.  
  238.     if(tsol>0)
  239.         {
  240.         update->which=(short *)malloc(tsol*sizeof(short));
  241.         if(!update->which) fatal_error("No memory left");
  242.         memcpy(update->which,temp,tsol*sizeof(short));
  243.         }
  244.  
  245.     update->hmprobs=probs;
  246.  
  247.     if(probs>0)
  248.         {
  249.         update->wprobs=(short *)malloc(probs*sizeof(short));
  250.         if(!update->wprobs) fatal_error("No memory left");
  251.         memcpy(update->wprobs,tprobs,probs*sizeof(short));
  252.         }
  253.  
  254.     free(tprobs);
  255.     free(temp);
  256.     }
  257.  
  258. void restore_solutions(struct up_solution *update,
  259.                               struct problem_list *pblist,struct board *board)
  260.     {
  261.     short x;
  262.  
  263.     if(update->hmprobs>0)
  264.         {
  265.         for(x=0;x<update->hmprobs;x++)
  266.             {
  267.             if(pblist->problem[update->wprobs[x]]->solved==NO) fatal_error("Something is wrong");
  268.             pblist->problem[update->wprobs[x]]->solved=NO;
  269.             }
  270.         free(update->wprobs);
  271.         }
  272.  
  273.     if(update->howmany>0)
  274.         {
  275.         for(x=0;x<update->howmany;x++)
  276.             {
  277.             if(board->solution[update->which[x]]->valid==YES) fatal_error("Something is wrong!");
  278.             board->solution[update->which[x]]->valid=YES;
  279.             }
  280.         free(update->which);
  281.         }
  282.     }
  283.  
  284. short solve_problem_list(struct problem_list *pblist,struct board *board,char **matrix)
  285.     {
  286.     struct up_solution update;
  287.     short x,mdp,answer,sols,j;
  288.  
  289.     find_most_difficult_problem(pblist,&sols,&mdp,board);
  290.  
  291.     if(mdp==-1) return YES;
  292.     if(sols==0) return NO;
  293.  
  294.     tempsolused++;
  295.     if(board->solused<tempsolused) board->solused=tempsolused;
  296.  
  297.     #ifdef DEBUG
  298.     dump_ddebug(board,pblist,mdp);
  299.     #endif
  300.  
  301.     answer=NO;
  302.     for(x=0;x<pblist->problem[mdp]->solnumb && answer==NO;x++)
  303.         {
  304.         j=pblist->problem[mdp]->solutions[x];
  305.         if(!board->solution[j]->valid) continue;
  306.  
  307.         pblist->problem[mdp]->solved=YES;
  308.         pblist->final[mdp]=j;
  309.  
  310.         #ifdef DEBUG
  311.         dump_debug(board,pblist,mdp);
  312.         #endif
  313.  
  314.         remove_solutions(&update,pblist,board,matrix,j);
  315.         answer=solve_problem_list(pblist,board,matrix);
  316.         restore_solutions(&update,pblist,board);
  317.  
  318.         if(answer==NO) pblist->final[mdp]=-1;
  319.         pblist->problem[mdp]->solved=NO;
  320.         }
  321.  
  322.     tempsolused--;
  323.  
  324.     return answer;
  325.     }
  326.  
  327. short problem_solver(struct board *board,char **matrix,short debug,FILE *h1)
  328.     {
  329.     short x,y,i,px,py,qx,qy,name,answer,k;
  330.     struct problem_list pblist;
  331.  
  332.     board->problem_solved=0;
  333.     board->solused=0;
  334.     tempsolused=0;
  335.  
  336.     build_problem_list(&pblist,board);
  337.     answer=solve_problem_list(&pblist,board,matrix);
  338.  
  339.     if(debug)
  340.         {
  341.         x=board->turn^SWITCHSIDE;
  342.  
  343.         if(!answer)
  344.             {
  345.             fprintf(h1,"It has not been possible to find a subset of rules which both satisfies\n");
  346.             fprintf(h1,"compatibility and full coverage of the problem list. Therefore nothing\n");
  347.             fprintf(h1,"can be said about %s possibilities\n\n",wside[x]);
  348.             goto PB_ENDING;
  349.             }
  350.  
  351.         fprintf(h1,"Sol. matching problem list for %s ",wside[x]);
  352.         fprintf(h1,"(according to rules compatibility):\n\n");
  353.  
  354.         for(x=0;x<pblist.number;x++)
  355.             {
  356.             fprintf(h1,"PG[%2d] %c%d-%c%d  ",x,
  357.                 board->xplace[pblist.problem[x]->group][0]+97,board->yplace[pblist.problem[x]->group][0]+1,
  358.                 board->xplace[pblist.problem[x]->group][3]+97,board->yplace[pblist.problem[x]->group][3]+1);
  359.  
  360.             i=pblist.final[x];
  361.             if(i==-1)
  362.                 {
  363.                 printf("    NOT FOUND\n\r");
  364.                 fprintf(h1,"    NOT FOUND\n");
  365.                 }
  366.             else
  367.                 {
  368.                 board->problem_solved++;
  369.                 name=board->solution[i]->solname;
  370.                 px=ELX(board->solution[i]->solpoint[0]);
  371.                 py=ELY(board->solution[i]->solpoint[0]);
  372.  
  373.                 qx=ELX(board->solution[i]->solpoint[1]);
  374.                 qy=ELY(board->solution[i]->solpoint[1]);
  375.  
  376.                 fprintf(h1,"%13s  ",rulename[name-1]);
  377.                 fprintf(h1,"%c%d-%c%d   ",px+97,py+1,qx+97,qy+1);
  378.                 fprintf(h1,"[%03d] {",i);
  379.  
  380.                 for(y=0;y<board->solution[i]->sqinvnumb;y++)
  381.                     {
  382.                     k=board->solution[i]->sqinv[y];
  383.                     fprintf(h1," %c%d",ELX(k)+97,ELY(k+1)+1);
  384.                     }
  385.  
  386.                 fprintf(h1," }\n");
  387.                 }
  388.             }
  389.         fprintf(h1,"\nThe aforementioned statements prove that ");
  390.  
  391.         x=board->turn^SWITCHSIDE;
  392.  
  393.         if(x==WHITE)
  394.             fprintf(h1,"white can win from this position.\n");
  395.         else
  396.             fprintf(h1,"black can at least draw the game\nfrom this position.\n");
  397.         }
  398.  
  399.     PB_ENDING:
  400.     remove_problem_list(&pblist);
  401.     return answer;
  402.     }
  403.